home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / swagd_f.zip / FAQ.SWG / 0016_Ins and Outs of Compress.pas < prev    next >
Pascal/Delphi Source File  |  1993-11-02  |  13KB  |  291 lines
  1. {
  2. Robert Rothenburg
  3.  
  4. Ok, since a few people have requested info about compression routines I
  5. thought some actual descriptions of the algorithm(s) involved would be a
  6. good idea.  Rather than dig out someone else's text file or mail (which
  7. might be copyrighted or arcane) I'll try my hand at explaining a few
  8. methods.
  9.  
  10. It seems better that programmers have at least a rudimentary understanding
  11. of the algortihms if they plan on using (or not using :) them.
  12.  
  13. DISCLAIMER: Please pardon any innacuracies: What I know is based on other
  14.   people's mail, text files or from what I've gleaned from spending a few
  15.   hours at the library (adivce: your local college research-library is a
  16.   wonderful resource of algorithms and source-code. Old magazines as well
  17.   as academic papers like the IEEE Transactions are worth examining).
  18.  
  19.  
  20. In this insanely long post:
  21.  
  22. I.   "Garbage Collection"
  23. II.  "Keywords"
  24. III. Run-Length Encoding (RLE)
  25. IV.  Static and Dynamic Huffmann Codes  <--(BTW, is it one or two n's?)
  26. V.   Lampev-Ziv (LZ)
  27. VI.  Lampev-Ziv-Welch (LZW) et al.
  28.  
  29.  
  30. I.  "Garbage Collection"
  31.  
  32.   The simplest methods of compression in weeding out unnecessary data,
  33.   especially from text files.  Spaces at the end of a line, or extra
  34.   carriage returns at the end of a file. (Especially with MS-DOS text
  35.   files, which use a Carriage Return *and* Line Feed--many editors and
  36.   file-browsers do not need both. Eliminating one of them can cut a large
  37.   text file's size by a few percent!)
  38.  
  39.   I've also seen some utilities that "clean up" the headers of EXE
  40.   files (such as UNP) by eliminating `unnecessary' info.  Other
  41.   utilities will clean up graphics files so that they'll compress
  42.   better.
  43.  
  44.   In fact, removing excess "garbage" from any file will probably
  45.   improve its compressability.
  46.  
  47. II. "Keywords"
  48.  
  49.   Another way to compress text files is to use a "keyword" for each word.
  50.  
  51.   I.E. we can assume most text files will have less than 65,536 different
  52.   words (16 bits=two bytes), and thus we can assign a different value for
  53.   each word: since most words are longer than three letters (more than two
  54.   bytes), we will save space in the file. However, we'll need some form of
  55.   look-up table for each keyword--one way around this might be to use a
  56.   reference to a standard dictionary file that is included with an operating
  57.   system or word processor.
  58.  
  59.   (This has other advantages as well. Many BASIC interpreters will store
  60.   commands like PRINT or INPUT as a character code rather than the entire
  61.   name in ASCII text.  Not only does this save memory but improves the
  62.   run-speed of the program.)
  63.  
  64.   This method can be adapted to other (non-text) files, of course.
  65.  
  66. III. Run-Length Encoding (RLE)
  67.  
  68.   With RLE, repeated characters (such as leading spaces in text, or large
  69.   areas of one color in graphics) are expressed with a code noting which
  70.   byte is repeated and how many times it's repeated.
  71.  
  72. IV.  Static and Dynamic Huffmann Codes
  73.  
  74.   The logic behind this method is that certain characters occur more often
  75.   than others, and thus the more common characters can be expressed with
  76.   fewer bits. For example, take a text file: 'e' might be the most common
  77.   character, then 'a', then 's', then 'i', etc....
  78.  
  79.   We can express these characters in a bit-stream like so:
  80.  
  81.                 'e' = 1
  82.                 'a' = 01         <--These are Static Huffmann Codes.
  83.                 's' = 001
  84.                 'i' = 0001
  85.                     etc...
  86.  
  87.   Since these characters normally take up 8-bits, the first (most common)
  88.   seven will save space when expressed this way, if they occur often enough
  89.   in relation to the other 249 characters.
  90.  
  91.   This is often represented as a (Static) Huffmann Tree:
  92.  
  93.                         /\              Note that a compression routine
  94.                  'e' = 1  0             will have to first scan the data
  95.                          / \            and count which characters are
  96.                   'a' = 1   0           more common and assign the codes
  97.                            /  \         appropriately.
  98.                    etc... 1    0
  99.                               /  \
  100.                                 etc...
  101.  
  102.   Notice that if we use the full 256 ASCII characters we'll run into
  103.   a problem with long strings of 0's.  We can get around that by using
  104.   RLE (Which is what the compressor SQUEEZE uses).
  105.  
  106.   Again, since most files use a large range of the character set, and
  107.   their occurences are much more "even", we can use use Dynamic Huffmann
  108.   Codes as an alternative.  They are like their static cousins, only after
  109.   the string of n zeros they are followed by n (binary) digits:
  110.  
  111.                 1        = 1                             1 character
  112.                01x       = 010, 011                      2 chars
  113.               001xx      = 00100, 00101, 00110, 0011     4 chars
  114.              0001xxx     = 0001000, 0001001 ... 0001111  8 chars
  115.                     etc...
  116.  
  117.   As you can guess, the Huffmann Tree would look something like:
  118.  
  119.                       /\            It's a bit too complicated to
  120.                      1  0           express with ASCII <g>
  121.                        / \
  122.                       1    0
  123.                      / \   /\
  124.                     1   0    etc...
  125.  
  126.   Huffmann Coding is based on how often an item (such as an ASCII
  127.   character) occurs, and not where or in relation to other items.
  128.   It's not the msot efficient mothod, but it is one of the simplest.
  129.   One only needs to make an initial pass to count the characters and
  130.   then re-pass translating them into the appropriate codes. No
  131.   pattern-matching or search routines are required.
  132.  
  133. V.  Lampev-Ziv (LZ) Encoding.
  134.  
  135.   This method _does_ require some fast pattern-matching/search routines.
  136.   It takes advantage of the fact that in most files (especially text)
  137.   whole strings of characters repeat themselves.
  138.  
  139.   Take this sample line of text:
  140.  
  141.       "THAT WHICH IS, IS. THAT WHICH IS NOT, IS NOT. IS IT? IT IS!"
  142.  
  143.   (Ok, so "Flowers for Algernon" was on TV the other night... :)
  144.   With LZ, we read in from the beginning of the file and keep adding
  145.   groups ("Windows") of characters that have not already occurred.
  146.   So we add the first sentence, then get to the second "IS"...instead
  147.   of repeating it we note that it's a duplicate, with a reference
  148.   to where the original occurred and how long the string is. (I.E. we note
  149.   that the "IS" occurred 4 characters previously, and is two characters
  150.   long.)
  151.  
  152.   This method can be tweaked by using a "Sliding Window" approach where the
  153.   largest matches are found...we can compress the second "IS" with the first,
  154.   but when don't gain much.  However the two "IS NOT"s, when matched against
  155.   each other, would compress better.
  156.  
  157.   Our compressed file will have two types of data: the raw characters and
  158.   the LZ-references (containing the pointer and length) to the raw
  159.   characters, or even to other LZ-references.
  160.  
  161.   One way to tweak this further is to compress the LZ-References using
  162.   Huffmann codes. (I think this is what's done with the ZIP algorithm.)
  163.  
  164. VI.  Lampev-Ziv-Welch (LZW) -- Not to be confused with LZ compression.
  165.  
  166.   This is the method used by Unix COMPRESS, as well as the GIF-graphics
  167.   file format.
  168.  
  169.   Like LZ, LZW compression can compress a stream of data on one-pass
  170.   relatively quickly (assuming you've got the fast search routines!).
  171.   However, LZW uses a hash table (essentially it's an array of strings,
  172.   also known as a string table), and a "match" is expressed as its index
  173.   in the hash table rather than a reference to where and how long the
  174.   match is.
  175.  
  176.   The input stream is read in, strings are assembled and sent out when
  177.   they are already in the hash table, or they are added to the hash table
  178.   and sent out in such a way that a decoder can still re-assemble the
  179.   file.
  180.  
  181.   Needless to say, this method is a memory hog.  Most compressors that
  182.   use this method are usually limited to a certain number of entries
  183.   in the hash-table (12- or 16-bits, or 4096 and 65536 respectively).
  184.  
  185.   Here's an outline of the LZW Compression Algorithm:
  186.  
  187.          0. a. Initialize the hash table. (That means for each possible
  188.                character there is one "root" entry in the table. Some
  189.                flavors of LZW may actually have a "null" non-character
  190.                at the base of the table.)
  191.             b. Initialize the "current" string (S) to null.
  192.  
  193.          1. Read a character (K) from the input stream.
  194.             (If there are none left, then we're done, of course.)
  195.  
  196.          2. Is the string S+K in the string-table?
  197.  
  198.          3. If yes, then a. S := S+K
  199.                          b. Go to Step 1.
  200.  
  201.             If no, then  a. add S+K to the string table.
  202.                          b. output the code for S
  203.                          c. S := K
  204.                          d. Go to Step 1.
  205.  
  206.   Decompression is very similar.
  207.  
  208.          0. a. Initialize the string table (the same as with compression).
  209.             b. Read the first code from the compressed file into C
  210.             c. Then output the equivalent string for code C
  211.             d. Let code O := code C (The code, not the string!)
  212.  
  213.          1. Read the next code from the input stream into C
  214.  
  215.          2. Does code C exist in the string/hash table?
  216.  
  217.          3. If yes, then a. output the string for code C
  218.                          b. S := equivalent string for code O
  219.                          c. K := first character of the string for code C
  220.                          d. add S+K to the string table
  221.  
  222.             If no, then  a. S := equivalent string for code O
  223.                          b. K := first character of S
  224.                          c. output S+K
  225.                          d. add S+K to the table
  226.  
  227.          4. code O := code C
  228.  
  229.          5. Go to Step 1.
  230.  
  231.   It may seem psychotic at first, but it works.  Just keep reading it and
  232.   thinking about it.  The best way is with a pencil and pad experimenting
  233.   with a character set of four characters (A, B, C, and D) and a "word"
  234.   like "ABACADABA" and following through the steps.
  235.  
  236.   (An actual walk-through is not included here, since it will take up
  237.   *way* too much space.  I recommend getting further, more detailed
  238.   descriptions of LZW if you plan on writing an implementation.)
  239.  
  240.   One important thing is to *not* confuse between the `code' for a string
  241.   (it's index in the hash table) and the string itself.
  242.  
  243.   Two points about LZW implementations:
  244.  
  245.       1. The code stream (i.e. the compressed output) is not usually
  246.          a set number of bits, but reflects how many entries are in
  247.          the string table.  This is another way to further compress
  248.          the data.
  249.  
  250.          Usually, LZW schemes will output the code in the number of bits
  251.          exactly reflecting the string table.  Thus for the first 512
  252.          codes the output is 9-bits.  Once the 513th string is added to
  253.          the table, it's 10-bits and so on.
  254.  
  255.          Some implementations will use a constant output until a threshold
  256.          is reached.  For example, the code output will always be 12-bits
  257.          until the 4097th string is added, then the code output is in
  258.          16-bit segments etc...
  259.  
  260.          If these scenarios are used, the decompression routine *must*
  261.          "think ahead" so as to read in the proper number of bits from
  262.          the encoded data.
  263.  
  264.       2. Because full string tables are incredible memory hogs, many
  265.          flavors of LZW will use a "hash" table (see, string and hash
  266.          table aren't quite the same).
  267.  
  268.          Instead of a string of characters like "ABC", there'll be
  269.          a table containing the last character of the string, and a
  270.          reference to the previous character(s).  Thus we'll have
  271.          "A", "[A]B" and "[[A]B]C" where [x] is the reference (or the
  272.          actual "code") for that character/string.  Using this method
  273.          may be slower, but it saves memory and makes the implement-
  274.          ation a little easier.
  275.   There are many variations on LZW using other sets of strings to
  276.   compare with the string table--this is based on the assumption that
  277.   the more entries there are in the table, the more efficient the
  278.   compression will be.
  279.  
  280.   One variation (Lampev-Ziv-Yakoo) would add the ButFirst(S+K) every
  281.   time S+K was added. "ButFirst" means all characters but the first
  282.   one. So ButFirst("ABCD") = "BCD".
  283.  
  284.  
  285. Anyhow, those are the compression algorithms that I know about which I
  286. can even remotely attempt to explain.
  287. I apologize for any (glaring?) mistakes. It's late...what started as a
  288. meaningless reply to somebody asking something about SQUEEZE exploded
  289. into this post.  I hope it's useful to anybody interested.
  290. }
  291.